package com.datastructure.algorithm.binarysearchnorecursion;
// 二分查找算法
public class BinarySearchNoRecur {

    public static void main(String[] args) {
        //测试
        int [] arr = {1,3,8,10,11,67,100};
        int index = binarySearch(arr,100);
        System.out.println("index=" + index);
    }

    // 二分查找的非递归的实现
    /**
     *
     * @param arr 待查找的数组,
     * @param target 需要查找的目标值
     * @return 返回对应下标，-1表示没有找到
     */
    public static int binarySearch(int[] arr, int target){

        int left = 0;
        int right = arr.length - 1;
        while (left <= right) { // 说明继续查找
            int mid = (left + right)/2;
            if(arr[mid] == target){
                return mid;
            } else if (arr[mid] > target){
                right = mid - 1;// 需要向左边查找
            } else {
                left = mid + 1; // 需要向右边查找
            }
        }
        return -1;
    }
}
